public class Main {
    /* https://leetcode-cn.com/problems/combination-sum/
     * 组合总和
     * 递增 加和
     * */
    public static void DFS(int[] candidates, int pre, List<List<Integer>> list, List<Integer> curRet, int curSum, int target) {
        if (curSum >= target) {
            if (curSum == target) {
                //保存当前解集
                list.add(new ArrayList<>(curRet));
            }
            return;
        }
        //累加的起始位置为上一项的位置
        for (int i = pre; i < candidates.length; i++) {
            //累加当前项
            curRet.add(candidates[i]);
            DFS(candidates, i, list, curRet, curSum + candidates[i], target);
            //回溯
            curRet.remove(curRet.size() - 1);
        }
    }

    public static List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> list = new ArrayList<>();
        List<Integer> curRet = new ArrayList<>();
        DFS(candidates, 0, list, curRet, 0, target);
        return list;
    }

    /*
     * 组合之和
     * 递减
     * */
    public static void DFS2(int[] candidates, int begin, List<List<Integer>> list, List<Integer> curRet, int target) {
        if (target < 0) {
            return;
        }
        if (target == 0) {
            list.add(new ArrayList<>(curRet));
            return;
        }
        for (int i = begin; i < candidates.length; i++) {
            if (target - candidates[i] < 0) {
                break;
            }
            curRet.add(candidates[i]);
            DFS2(candidates, i, list, curRet, target - candidates[i]);
            curRet.remove(curRet.size() - 1);
        }
    }

    public static List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> list = new ArrayList<>();
        List<Integer> curRet = new ArrayList<>();
        Arrays.sort(candidates);
        DFS2(candidates, 0, list, curRet, target);
        return list;
    }

    /*
     * 组合之和
     *
     * */
    public static void DFS3(int[] candidates, int begin, List<List<Integer>> list, List<Integer> curRet, int curSum, int target) {
//剪枝
//        if(curSum > target){
//            return;
//        }
        if (curSum == target) {
            list.add(new ArrayList<>(curRet));
        }
        for (int i = begin; i < candidates.length; i++) {
            if (curSum + candidates[i] > 0) {
                break;
            }
            curRet.add(candidates[i]);
            DFS3(candidates, i, list, curRet, curSum + candidates[i], target);
            curRet.remove(curRet.size() - 1);
        }
    }

    public static List<List<Integer>> combinationSum3(int[] candidates, int target) {
        List<List<Integer>> list = new ArrayList<>();
        List<Integer> curRet = new ArrayList<>();
//      Arrays.sort(candidates);
        DFS3(candidates, 0, list, curRet, 0, target);
        return list;
    }
}